NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/8018

Internet Message Format | 1996-08-05 | 1.3 KB

Path: anvil.ugrad.cs.ubc.ca!not-for-mail
From: [e-mail] (Kazimir Kylheku)
Newsgroups: comp.lang.c
Subject: Re: merge algorithm
Date: 28 Feb 1996 15:44:31 -0800
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
Message-ID: <[e-mail]>
References: <[e-mail]>
NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca

In article <[e-mail]>,
Joe E. Coffland <[e-mail]> wrote:
 >I am trying to find an algorithm to merge two sorted arrays containing
 >n elements.
 >ie. A[1] <= A[2]<= ... <= A[m] and A[m+1] <= A[m+2] <= ... <A[n]
 >The algorithm must run in O(n) time and require only a small amount of
 >fixed additional memory regardless of the size of m or n. I have reason
 >to believe that there is such an algorithm but I have only been able to
 >find algorithms that meet the memory restriction but run in at best
 >O(nlogn) and are recursive (which can through some work of course be
 >changed in to an iterative algorithm). If any one can point me to a book
 >or any other source of information on the subject or just get me headed
 >in the right direction it would be greatly appriciated.

That's an interesting problem. One possible ``lead'' might be to reverse one of
the arrays in place first, and then look for solutions given that arrangement
of things.
--